package com.leecode.base;

/**
 * @ClassName Index_16_交换类_快速排序
 * @Author bsy
 * @Description 选定一个数为基准，比基准小的元素全放在基准左边，比基准大的元素全放在基准右边，
 * 左边和右边又递归重复上述过程，直到所有元素都排列在相应位置上。
 * 是一种基于二叉树结构的交换排序
 * @Date 2023/2/19 16:38
 * @Version 1.0
 */
public class Index_16_快速排序 {


    public static void main(String[] args) {
       int[] nums = {5,6,3,5,9,1,4};
        int[] ints = quickSort(nums, 0, 6);
        ArrayUtil.printArray(ints);
    }


    /**
     * 基于二叉树实现的
     * @param nums
     * @param L
     * @param R
     * @return
     */
    public static int[] quickSort(int[] nums, int L, int R) {
        int partitionIndex;  // 分区位置
        int left = L;
        int right = R;
        if (left < right) {
            partitionIndex = partition(nums, left, right);
            quickSort(nums, left, partitionIndex - 1);
            quickSort(nums, partitionIndex + 1, right);
        }
        return nums;
    }


    /**
     * 分区操作，找到分区位置
     *
     * @param nums
     * @return
     */
    public static int partition(int[] nums, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;

        //这波操作以后，右侧的数已经有序，而且基准值
        for (int i = index; i <= right; i++) {
            if (nums[i] < nums[pivot]) {
                swap(nums, i, index);
                index++;
            }
        }
        swap(nums, pivot, index - 1);
        return index - 1;
    }


    /**
     * 交换用的
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
